package 题目集.二分;

import org.junit.Test;

/**
 * https://leetcode.cn/problems/max-consecutive-ones-iii/description/
 * 给定一个二进制数组 nums 和一个整数 k，假设最多可以翻转 k 个 0 ，则返回执行操作后 数组中连续 1 的最大个数 。
 */
public class demo08_最大连续1的个数 {

    /**
     * 第一思路：枚举数组中每个0翻或不翻的情况，枚举复杂度O(2^n)，找到其最大连续1的数量O(n)，总体复杂度O(n*2^n)
     * 第二思路：二分长度，设长度为m，验证是否存在长度为m且符合条件的区间。验证的方式是查看该区间内0的个数<=k,这个可以通过前缀和快速得到
     * 第三思路：滑动窗口{@link 题目集.滑动窗口.ch02_不定长窗口.demo08_最大连续1的个数#longestOnes(int[], int)}
     */
    int[] sum;  //前缀和存储1的个数
    int k;

    public int longestOnes(int[] nums, int k) {
        this.k = k;
        sum = new int[nums.length + 1];
        for (int i = 1; i < sum.length; i++) {
            sum[i] = sum[i - 1] + nums[i - 1];
        }

        int l = 0, r = nums.length;
        while (l <= r) {
            int m = l + r >> 1;
            if (check(m)) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        return Math.max(r, 0);
    }

    public boolean check(int m) {
        //区间内最少需要m-k个1
        int min = m - k;
        for (int i = m; i < sum.length; i++) {
            int cnt = sum[i] - sum[i - m];
            if (cnt >= min) return true;
        }
        return false;
    }

    @Test
    public void t1() {
        int[] nums = {0, 0, 0, 1};
        int k = 4;
        System.out.println(longestOnes(nums, k));
    }
}
